// N-queens
function solveNQueens(n) {
  if (n < 1) return []
  let result = []
  let cols = new Set()
  let pie = new Set()
  let na = new Set()

  function dfs(n, row, curState) {
    if (row >= n) {
      return result.push(curState)
    }

    for (let col = 0; col < n; col++) {
      if (cols.has(col) || pie.has(row + col) || na.has(row - col)) {
        continue
      }

      cols.add(col)
      pie.add(row + col)
      na.add(row - col)
      dfs(n, row + 1, curState.concat([col]))

      cols.delete(col)
      pie.delete(row + col)
      na.delete(row - col)
    }
  }

  dfs(n, 0, [])
  console.log(result)
  return generateResult(n, result)
}

solveNQueens(4)

function generateResult(n, result) {
  let r = []
  for (let arr of result) {
    let board = []
    for (let v of arr) {
      board.push('.'.repeat(v) + 'Q' + '.'.repeat(n - v - 1))
    }
    r.push(board)
  }
  console.log(r)

  return r
}

function solveNQueens2(n) {
  let result = []
  let pie = []
  let na = []
  let col = []

  function dfs(n, row, arr) {
    if (row >= n) {
      return result.push(arr)
    }
    for (let i = 0; i < n; i++) {
      if (col[i] || pie[row + i] || na[i - row]) {
        continue
      }
      col[i] = 1
      pie[i + row] = 1
      na[i - row] = 1
      dfs(n, row + 1, arr.concat([i]))
      Reflect.deleteProperty(col, i)
      Reflect.deleteProperty(pie, i + row)
      Reflect.deleteProperty(na, i - row)
      //   col[i] = void 0
      //   pie[i + row] = void 0
      //   na[i - row] = void 0
    }
  }

  dfs(n, 0, [])
  console.log(result)
}
solveNQueens2(4)
